Chasing robbers on random graphs: Zigzag theorem

In this paper, we study the vertex pursuit game of Cops and Robbers where cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is the cop number of G. We present asymptotic results for the game of Cops and Robber played on a random graph G(n,p) for a wide range of p = p(n). It has been shown that the cop number as a function of an average degree forms an intriguing zigzag shape. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Maximum Orbit Weights in the σ-game and Lit-only σ-game on Grids and Graphs

Let G be a graph in which each vertex can be in one of two states: on or off. In the σ-game, when you “push” a vertex v you change the state of all of its neighbors, while in the σ⁺-game you change the state of v as well. Given a starting configuration of on vertices, the object of both games is to reduce it, by a sequence of pushes, to the smallest possible number of on vertices. We show that any starting configuration in a graph with no isolated vertices can, by a sequence of pushes, be reduced to at most half on, and we characterize those graphs for which you cannot do better. The proofs use techniques from coding theory. In the lit-only versions of these two games, you can only push vertices which are on. We obtain some results on the minimum number of on vertices one can obtain in grid graphs in the regular and lit-only versions of both games.     

PROPERTIES OF FRACTIONAL κ-FACTORS OF GRAPHS

In this paper the properties of some maximum fractional [0, κ]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional k-factors is obtained.     

On the structure of k-connected graphs without Kk-minor

Suppose G is a k-connected graph that does not contain K_k as a minor. What does G look like? This question is motivated by Hadwiger’s conjecture (Vierteljahrsschr. Naturforsch. Ges. Zürich 88 (1943) 133) and a deep result of Robertson and Seymour (J. Combin. Theory Ser. B. 89 (2003) 43).It is easy to see that such a graph cannot contain a (k−1)-clique, but could contain a (k−2)-clique, as K_k−5+G′, where G′ is a 5-connected planar graph, shows. In this paper, however, we will prove that such a graph cannot contain three “nearly” disjoint (k−2)-cliques. This theorem generalizes some early results by Robertson et al. (Combinatorica 13 (1993) 279) and Kawarabayashi and Toft (Combinatorica (in press)).     

接近零的Bool幂等阵

We establish a characterization theorem for a nearly zero Boolean idempotent matnx.     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

Degree sequence and supereulerian graphs

A sequence d=(d₁,d₂,…,d_n) is graphic if there is a simple graph G with degree sequence d, and such a graph G is called a realization of d. A graphic sequence d is line-hamiltonian if d has a realization G such that L(G) is hamiltonian, and is supereulerian if d has a realization G with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence d=(d₁,d₂,…,d_n) has a supereulerian realization if and only if d_n≥2 and that d is line-hamiltonian if and only if either d₁=n−1, or ∑_di=1d_i≤∑_dj≥2(d_j−2).     

On asymptotic summation of potentially oscillatory difference systems

A new technique for the asymptotic summation of linear systems of difference equations Y(t+1)=(D(t)+R(t))Y(t) is derived. A fundamental solution Y(t)=Φ(t)(I+P(t)) is constructed in terms of a product of two matrix functions. The first function Φ(t) is a product of the diagonal part D(t). The second matrix I+P(t), is a perturbation of the identity matrix I. Conditions are given on the matrix D(t)+R(t) that allow us to represent I+P(t) as an absolutely convergent resolvent series without imposing stringent conditions on R(t). Our method could be applied to discretized version of singularly perturbed differential equations Y^′(t)=A(t)Y(t) that fit the setting of quantum mechanics.     

Asymptotic energy of lattices

The energy of a simple graph G arising in chemical physics, denoted by E(G), is defined as the sum of the absolute values of eigenvalues of G. As the dimer problem and spanning trees problem in statistical physics, in this paper we propose the energy per vertex problem for lattice systems. In general for a type of lattice in statistical physics, to compute the entropy constant with toroidal, cylindrical, Mobius-band, Klein-bottle, and free boundary conditions are different tasks with different hardness and may have different solutions. We show that the energy per vertex of plane lattices is independent of the toroidal, cylindrical, Mobius-band, Klein-bottle, and free boundary conditions. In particular, the asymptotic formulae of energies of the triangular, 3³.4², and hexagonal lattices with toroidal, cylindrical, Mobius-band, Klein-bottle, and free boundary conditions are obtained explicitly.